package com.culture.bootdemo.算法;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: wen
 * @DateTime: 2024-12-05 17:25
 * @Description: lru最少使用淘汰算法
 * 使用一个双向链表存储缓存数据，按访问顺序排列。
 * 使用一个哈希表存储键到链表节点的映射，用于快速查找。
 **/
public class LRUCache {
    // 双向链表节点定义
    private static class Node {
        int key, value;
        Node prev, next;

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int capacity; // 缓存容量
    private final HashMap<Integer, Node> map; // 哈希表，存储 key 和节点的映射
    private final Node head, tail; // 虚拟头尾节点，用于方便操作链表

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.head = new Node(-1, -1); // 虚拟头节点
        this.tail = new Node(-1, -1); // 虚拟尾节点
        head.next = tail; // 初始化链表
        tail.prev = head;
    }

    // 获取缓存数据
    public int get(int key) {
        Node node = map.get(key);
        if (node == null) {
            return -1; // 如果不存在，返回 -1
        }
        // 存在，将节点移到链表头部
        moveToHead(node);
        return node.value;
    }

    // 插入或更新缓存数据
    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            // 如果 key 已存在，更新值，并将节点移到头部
            node.value = value;
            moveToHead(node);
        } else {
            // 如果 key 不存在，创建新节点
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            addToHead(newNode);

            if (map.size() > capacity) {
                // 缓存已满，移除链表尾部的节点
                Node tailNode = removeTail();
                map.remove(tailNode.key);
            }
        }
    }

    // 将节点移到链表头部
    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

    // 添加节点到链表头部
    private void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    // 移除链表中的节点
    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    // 移除链表尾部节点，并返回该节点
    private Node removeTail() {
        Node tailNode = tail.prev;
        removeNode(tailNode);
        return tailNode;
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(3);

        cache.put(1, 1); // 缓存：1
        cache.put(2, 2); // 缓存：2 -> 1
        cache.put(3, 3); // 缓存：3 -> 2 -> 1
        System.out.println(cache.get(1)); // 输出：1，缓存：1 -> 3 -> 2
        cache.put(4, 4); // 缓存：4 -> 1 -> 3，移除 2
        System.out.println(cache.get(2)); // 输出：-1（2 被移除）
        cache.put(5, 5); // 缓存：5 -> 4 -> 1，移除 3
        System.out.println(cache.get(3)); // 输出：-1（3 被移除）
        System.out.println(cache.get(4)); // 输出：4，缓存：4 -> 5 -> 1
    }

}

